#include <iostream>

using namespace std;
// 找到target，返回索引，找不到，返回-1
template<typename T>
int binarySearch(T arr[], int n, T target){

    //在arr[l...r]中查找target
    int l=0, r=n-1;
    while(l<=r){

       // int mid = (l+r)/2;
        int mid = l+(r+l)/2;
        if(arr[mid] == target)
            return mid;
        if(target<arr[mid])
            r = mid - 1;
        else l = mid+1;
    }
    return -1;
}
